//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 
//
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 
//
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
//
// 示例： 
//
// 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 0 -> 8
//原因：342 + 465 = 807
// 
// Related Topics 链表 数学 
// 👍 4662 👎 0

package com.beikai.springbootleetcodedemo.demo01.leetcode.editor.cn;

import lombok.Data;
import org.junit.Test;

public class AddTwoNumbers {
    public static void main(String[] args) {
        Solution solution = new AddTwoNumbers().new Solution();

    }

    @Test
    public void test(){
        Solution solution = new AddTwoNumbers().new Solution();
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(3);
        listNode2.setNext(listNode3);
        listNode1.setNext(listNode2);

        ListNode listNode4 = new ListNode(5);
        ListNode listNode5 = new ListNode(6);
        ListNode listNode6 = new ListNode(4);
        listNode5.setNext(listNode6);
        listNode4.setNext(listNode5);

        ListNode listNode = solution.addTwoNumbers(listNode1, listNode4);

        while (null != listNode){
            System.out.println(listNode.getVal());
            listNode = listNode.next;
        }
    }

    @Data
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }


    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     */


    class Solution {
        /**{
         * 思路 :
         *  1 题中要求输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
         *   其实可以理解 反向 ab 到ba 然后在转到 ab ,那就是不转了
         *
         *  2 同时便利每一个链表元素,对元素的值相加,如果和超过10,存到 tempCarry 中,用来进一位的计算,
         *    然后存到结果的链表中
         *
         *  3 由于链表的第一个元素是0 ,所以返回结果的时候返回第二个之后的元素.
         */
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

            // 创建临时链表,用来存储当前的结果
            ListNode result = new ListNode(0);
            ListNode temp01 = l1,temp02 = l2,curr = result;
            // 创建用来进位的变量
            int tempCarry = 0;
            while (temp01 != null || temp02 != null){
                // 分别获取两个链表当前的值
                int value01 = temp01 == null ? 0:temp01.val;
                int value02 = temp02 == null ? 0:temp02.val;

                // 计算当前两个链表相加的值
                int sum = value01 + value02 + tempCarry;
                // 获取进位的值
                // 方式 1   执行耗时:3 ms,击败了21.65% 的Java用户
                // tempCarry = sum / 10;
                // 方式 2 使用 比较的方式比 使用除法 更节省时间  执行耗时:2 ms,击败了99.90% 的Java用户
                tempCarry = sum > 9 ? 1 : 0;
                // 获取结果当前的值
                int currValue = sum % 10;

                // 创建链表元素
                ListNode newListNode = new ListNode(currValue);
                // 设置链表的下一个
                curr.next = newListNode;
                // 把下一个listnode 指向 curr
                curr = newListNode;

                // l1 和 l2 的链表 移动到下一个
                temp01 = temp01 == null ? null:temp01.next;
                temp02 = temp02 == null ? null:temp02.next;

            }
            // 这一步流掉了
            if (tempCarry > 0) {
                curr.next = new ListNode(tempCarry);
            }

            return result.next;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


    /**{
     * 自己的方式 (不能使用第三方函数库)
     *
     *  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
     *             String params1 = getList(l1);
     *             String params2 = getList(l2);
     *
     *             String string = new BigDecimal(params1).add(new BigDecimal(params2)).toString();
     *
     *             char[] chars = string.toCharArray();
     *             ListNode newListNode = null;
     *             for (char aChar : chars) {
     *                 if (null == newListNode) {
     *                     newListNode = new ListNode(Integer.parseInt(aChar+""));
     *                 }else {
     *                     ListNode listNode = new ListNode(Integer.parseInt(aChar+""));
     *                     listNode.setNext(newListNode);
     *                     newListNode = listNode;
     *                 }
     *             }
     *
     *             return newListNode;
     *         }
     *
     *         String getList(ListNode listNode) {
     *             StringBuilder stringBuilder = new StringBuilder();
     *             while (listNode != null) {
     *                 stringBuilder.append(listNode.getVal());
     *                 listNode = listNode.next;
     *             }
     *             return stringBuilder.reverse().toString();
     *         }
     *     }
     */


}